The present invention relates to a method for identifying betrayers of proprietary data, i.e., authorized users who without authorization pass on proprietary data, the proprietary data being encrypted.
In modern information technology, it is becoming increasingly important to be able to distribute proprietary data as secure data to an authorized group of customers. Examples of this are digital pay-TV, data broadcasting, data distribution using CD-ROM, and fee-based online databases.
In all the aforementioned media, the information is distributed in encrypted form. It is customary that several authorized persons are able to decrypt this information. In practice, it is frequently the case that such proprietary data is passed on, or retransmitted without authorization to third parties. In the systems used today, it is not possible to detect the source of this type of unauthorized passing-on, or redistribution.
A first approach to solving this problem is discussed in the article xe2x80x9cTracing Traitorsxe2x80x9d by Chor, Fiat and Naor, published in the Proceedings on CRYPTO 194 (Springer Heidelberg, Lecture Notes in Computer Science 839). This article is hereby incorporated by reference herein. The article presents a probabilistic method for developing a so-called xe2x80x9ctraitor tracingxe2x80x9d strategy, which can be used to find xe2x80x9ctraitorxe2x80x9d, even if he is in collusion with up to kxe2x88x921 other traitors (the article refers to this property as k-resilient).
Here, xe2x80x9cprobabilisticxe2x80x9d means that virtually all the values in such a strategy are randomly selected. This is a disadvantage when the results of such a strategy are used in court proceedings against a person who has passed on proprietary information, without authorization. A technical report prepared by an expert that is based on probabilities has little prospect of being accepted as evidence.
One of the core aspects of the strategy described in the aforementioned article is the fact that communication session key S, which is used to encrypt the data, is divided into t subkeys s1, . . . ,st. The session key S can only be reconstructed with knowledge of all t parts. Each of these subkeys s1, . . . ,st is then encrypted using each encryption key from a set of encryption keys PK, and the entirety of these cryptograms is placed in front of, or upstream of the data as a so-called xe2x80x9caccess blockxe2x80x9d. Each authorized user, or subscriber U receives a subset of encryption keys PK(U)⊂PK, which enables him to calculate all the subkeys s1, . . . ,st.
A property of these subsets PK(U) of encryption keys is that no combination of up to k of these subsets contains another subset in its entirety. This is a necessary precondition of the property of k-resilience.
An object of the present invention is to provide a method for identifying betrayers, or traitors of proprietary data, making it possible to identify unequivocally at least one betrayer {overscore (U)} (i.e., an authorized user U who has, without authorization, passed on one of his subkeys to a third person), the identification method thus being acceptable as unequivocal evidence in court proceedings.
The present invention provides a method for identifying at least one betrayer of proprietary data, the method including encrypting the proprietary data using a session key; dividing the session key into a plurality of subkeys, all of the plurality of subkeys being required to reconstruct the session key; encrypting each of the plurality of subkeys using each encryption key of a plurality of encryption keys so as to form a plurality of cryptograms; placing the plurality of cryptograms in front of the proprietary data as an access block; and assigning a respective subset of the plurality of encryption keys to each of a plurality of authorized users in accordance with at least one finite geometry structure and at least one finite geometry method so as to enable each user to reconstruct the plurality of subkeys and so as to ensure a k-resilience property for unequivocally identifying the at least one betrayer using a betrayer-search algorithm, k being a maximum number of betrayers in the at least one betrayer. As in the known method described above in a method according to the present invention, data to be encrypted are encrypted using a session key S. The session key S is subdivided into t subkeys s1, . . . ,st, all of which are required to reconstruct the session key S. Each subkey s1, . . . ,st is encrypted using each encryption key PK from the set of encryption keys PK. The entirety of such cryptograms is placed as an access block in front of the data to be encrypted.
A method according to the present invention includes a search strategy which differs in its deterministic construction from the search strategy of the previously described method.
According to the present invention, encryption keys PK are assigned to authorized users U in accordance with geometrical structures and methods of finite geometry. Each authorized user U is allocated a subset of encryption keys PK(U) which enables him to reconstruct in each case one of subkeys si for i=1, . . . t and, thus, also the session key S. Assigning the encryption keys according to geometrical structures and finite geometry methods ensures that every k authorized users have a total of no more than                     "LeftBracketingBar"                  PK          ⁡                      (            U            )                          "RightBracketingBar"            k        -          xe2x80x83        ⁢    1              encrypti      ⁢      on        ⁢          xe2x80x83        ⁢    keys    ⁢          xe2x80x83        ⁢    in    ⁢          xe2x80x83        ⁢    common    ⁢          xe2x80x83        ⁢    with    ⁢          xe2x80x83        ⁢    each    ⁢          xe2x80x83        ⁢    other    ⁢          xe2x80x83        ⁢    authorized    ⁢          xe2x80x83        ⁢          user      .      
Consequently, the k-resilience property, required for identifying a betrayer {overscore (U)}, is ensured. At least one betrayer {overscore (U)} can then be identified with certainty using a betrayer-search algorithm.
According to an embodiment of the present invention, the session key may be divided into t subkeys s1, . . . ,st using a threshold method so that the session key is reconstructable using one of the subkeys. The threshold method may be, for example, an r, t threshold method. The method according to the present invention is described in greater detail in the following on the basis of an exemplary embodiment, the finite geometry structure used being conceived as a finite affine space AG. Such geometrical concepts are described in A. Beutelspacher, U. Rosenbaum, Projektive Geometrie [Projective Geometry], Vieweg Publishers, Wiesbaden 1992, which is hereby incorporated by reference herein.